package com.linyaonan.leetcode.easy._1005;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
 * <p>
 * 以这种方式修改数组后，返回数组可能的最大和。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：A = [4,2,3], K = 1
 * 输出：5
 * 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
 * 示例 2：
 * <p>
 * 输入：A = [3,-1,0,2], K = 3
 * 输出：6
 * 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
 * 示例 3：
 * <p>
 * 输入：A = [2,-3,-1,5,-4], K = 2
 * 输出：13
 * 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= A.length <= 10000
 * 1 <= K <= 10000
 * -100 <= A[i] <= 100
 *
 * @author: Lin
 * @date: 2020/1/13
 */
public class MaximizeSum {

    public int largestSumAfterKNegations(int[] A, int K) {
        List<Integer> zheng = new ArrayList<>();
        List<Integer> fu = new ArrayList<>();
        int sum = 0;
        int min = A[0];
        for (int i : A) {
            if (i < 0) {
                fu.add(i);
            } else {
                zheng.add(i);
            }
            sum += i;
            if (i < min) {
                min = i;
            }
        }
        boolean oddK = K % 2 == 0;
        // 全部大于等于零
        if (fu.size() == 0) {
            if (oddK) {
                return sum;
            } else {
                sum -= (2 * min);
                return sum;
            }
        } else {
            // 负数值小于K
            if (fu.size() < K) {
                // 剩余的K为偶数，不操作即可
                if ((K - fu.size()) % 2 == 0) {
                    for (Integer i : fu) {
                        sum -= i * 2;
                    }
                    return sum;
                } else {
                    // 剩余的K为奇数，只操作一次，找出最小的正数
                    int tsum = 0;
                    int thisMin = zheng.get(0);
                    for (Integer i : zheng) {
                        if (i < thisMin) {
                            thisMin = i;
                        }
                        tsum += i;
                    }
                    // 这块需要注意有可能负数翻转后的整数就是最小的正数了
                    for (Integer i : fu) {
                        tsum -= i;
                        thisMin = Math.min(0 - i, thisMin);
                    }
                    tsum -= thisMin * 2;
                    return tsum;
                }
            } else {
                // 负数值大于等于K，最小的K个数直接翻转
                Collections.sort(fu);
                for (int i = 0; i < K; i++) {
                    sum -= fu.get(i) * 2;
                }
                return sum;
            }
        }
    }

}
